package main.java.sort;

/**
 * @Author: 郑国荣
 * @Date: 2023-10-04-14:24
 * @Description:
 */
public class CountingSort {

        public void countingSort(int[] arr){
            int n = arr.length;
            if (n<2) return;

            //找出数组中的最大值
            int max = arr[0];
            for (int i = 1; i < n; i++) {
                if (arr[i]>max) max = arr[i];
            }
            //创建桶
            int[] bucket = new int[max+1];
            for (int i = 0; i < n; i++) {
                bucket[arr[i]]++;
            }
            //遍历桶
            int index = 0;
            for (int i = 0; i < bucket.length; i++) {
                //如果桶中有元素，就将桶中的元素放入原数组
                while (bucket[i]>0){
                    arr[index++] = i;
                    bucket[i]--;
                }
            }
        }

        public static void main(String[] args) {
            int[] arr = {1,3,2,5,4,7,6};
            new CountingSort().countingSort(arr);
            for (int i : arr) {
                System.out.println(i);
            }
        }
}
